package com.zet.algorithm;

/**
 * 插入排序算法
 *
 * 直接插入排序的时间复杂度是O(N2)：假设被排序的数列中有N个数，遍历一趟时间复杂度是O(N)，
 * 需遍历多少次呢？N-1次，因此，其时间复杂度是O(N2)。

 直接插入排序是稳定的算法，它满足稳定算法的定义：假设在数列中存在a[i]=a[j]，若在排序之前
 ，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！

 * @Author: zet
 * @Date: 2018-03-25 21:33
 */
public class InsertSort {

    /**
     * 排序
     * @param arr 待排序的数组
     * @return 有序数组
     */
    public static int[] sort(int[] arr){
        int len = arr.length;

        int i,j,k;
        for (i = 1; i < len; i++) {
            for (j = i-1; j >= 0; j--) {
                if (arr[j] < arr[i])
                    break;
            }

            if (j != i - 1) {
                int temp = arr[i];
                for (k = i - 1; k > j; k--) {
                    arr[k + 1] = arr[k];
                }

                arr[k + 1] = temp;
            }
        }

        return arr;
    }
}
